/*
 * @lc app=leetcode.cn id=870 lang=typescript
 *
 * [870] 优势洗牌
 */

// @lc code=start
function advantageCount(nums1: number[], nums2: number[]): number[] {
  const n = nums1.length;
  const idxs = new Array<number>(n).fill(0).map((_, i) => i);
  // 升序排序，nums2 相对位置有用，采用索引排序
  idxs.sort((a, b) => nums2[a] - nums2[b]);
  nums1.sort((a, b) => a - b);

  const ans = new Array<number>(n);
  let l = 0;
  let r = n - 1;
  for (let i = 0; i < n; i++) {
    // nums1 首个元素大于 nums2 首个元素，保持优势
    if (nums1[i] > nums2[idxs[l]]) {
      ans[idxs[l++]] = nums1[i];
    } else {
      // 否则，将nums1首个元素和 num2最大的元素匹配
      ans[idxs[r--]] = nums1[i];
    }
  }
  return ans;
}
// @lc code=end
